A Heap is a specialized tree-based data structure.

  • It's the perfect data structure for implementing an efficient Priority Queue.
  • A heap allows for both fast insertion and fast extraction of the max/min element.

Goal

Achieve better than $O(n)$ for both operations. Ideally, something like $O(\log n)$.

$$\text{insert} \rightarrow O(\log n)$$
$$\text{extractMax} \rightarrow O(\log n)$$